package code;

import java.util.HashMap;

public class Code_742 {


    public static void  main(String[] args){

        Code_742 code_742 = new Code_742();

        System.out.println(code_742.champagneTower(100000009,33,17));
    }
    // 方法使用回溯法

    public double champagneTower(int poured, int query_row, int query_glass) {
        if(poured == 0 || query_glass > query_row){
            return 0;
        }

        // map<String,Node> K 节点位置 V 节点
        HashMap<String,Node> nodeMap = new HashMap<>();

        // 如果是出需要选择节点是首节点
        if(query_row == 0){
            if(poured > 1){
                return 1;
            }
        }


        // 初始化map
        //填装首节点
        nodeMap.put(getKey(0,0), new Node(0,0,1, poured ));
        nodeMap.put(getKey(query_row,query_glass), new Node(query_row,query_glass,1,0));
        //进行回溯遍历，获取所有路径
        findFatherNode(nodeMap,query_row,query_glass);

        //从首节点开始往下找子节点进行遍历处理
        pouredWine(nodeMap, nodeMap.get(getKey(0,0)),query_row,query_glass);

        double convertedCapacity = nodeMap.get(getKey(query_row,query_glass)).convertedCapacity;
        double capacity = nodeMap.get(getKey(query_row,query_glass)).capacity;
        return convertedCapacity / capacity;
    }

    public String getKey(int i ,int j){
        return i + "-" + j;
    }

    /**  */
    public void findFatherNode(HashMap<String,Node> nodeMap, int i, int j){
        if(nodeMap == null || nodeMap.size() < 1 || i < j || i < 0 || j < 0){
            return;
        }

        --i;
        // 处理行
        if(i > 0){
            for(int z = 0; z < 2; z++){
                // z=0 处理左节点 z=1 处理右节点
                if(-1 < j && j <= i){
                    nodeMap.put(getKey(i,j),new Node(i,j,1, 0));
                    findFatherNode(nodeMap,i,j);
                }
                --j;
            }

        }
    }

    public void pouredWine(HashMap<String,Node> nodeMap, Node node,int query_row, int query_glass){
        if(node == null){
            return;
        }

        // 先计算当前节点
        double moreCapacity = node.convertedCapacity - node.capacity;

        // 没有剩余的酒可以往下倒
        if(moreCapacity <= 0){
            return;
        }

        moreCapacity = moreCapacity / 2;

        int i = node.i + 1;
        int j = node.j;

        //已经超过了需要寻找的节点
        if(i > query_row){
            return;
        }

        // 查找子节点
        for(int z = 0; z < 2; z++){

            // z=0 处理左子节点 z=1 处理右子节点
            if(-1 < j && j <= i){
                // 寻找节点
                Node childNode = nodeMap.get(getKey(i,j));
                if(childNode != null){
                    childNode.convertedCapacity += moreCapacity;
                    pouredWine(nodeMap,childNode,query_row,query_glass);
                }
            }
            ++j;
        }
    }

    class Node{
        public int i;
        public int j;
        public double capacity;
        public double convertedCapacity;

        public Node(int i, int j, double capacity, double convertedCapacity){
            this.i = i;
            this.j = j;
            this.capacity = capacity;
            this.convertedCapacity = convertedCapacity;
        }
    }
}
